package jtg.trie;

import soot.Unit;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TrieTree {
    public TrieNode root;

    public int num;

    public TrieTree() {
        this.root = new TrieNode(null,false);
        this.num = 0;
    }

    public void insert(List<Unit> nums) {
        TrieNode cur = root;
        for (Unit num : nums) {
            if (!cur.children.containsKey(num)) {
//                System.out.println(num);
                cur.children.put(num, new TrieNode(num,false));
            }
            cur = cur.children.get(num);
        }
    }

    public TrieNode search(List<Unit> nums) {
        TrieNode cur = root;
        for (Unit num : nums) {
            if (!cur.children.containsKey(num)) {
                return null;
            }
            cur = cur.children.get(num);
        }
        return cur;
    }

    public TrieNode startWith(List<Unit> nums) {
        TrieNode cur = root;
        for (Unit num : nums) {
            if (!cur.children.containsKey(num)) {
                return null;
            }
            cur = cur.children.get(num);
            if(cur.children.isEmpty()&&!cur.isVisited){
                return cur;
            }
        }
        return null;
    }

    public int[] calTreeNode(){
        return new int[]{calLeaf(root),calVisited(root)};
    }

    public int calVisited(TrieNode root){
        if(root == null){
            return 0;
        }
        if(root.isVisited){
            return 1;
        }
        int sum = 0;
        for(TrieNode child : root.children.values()){
            sum += calVisited(child);
        }
        return sum;
    }

    public int calLeaf(TrieNode root){
        if(root == null){
            return 0;
        }
        if(root.children.isEmpty()){
            return 1;
        }
        int sum = 0;
        for(TrieNode child : root.children.values()){
            sum += calLeaf(child);
        }
        return sum;
    }

    public  List<List<Unit>> getAllBranch( List<Unit> path, TrieNode rt, List<TrieNode> visited){
        List<List<Unit>> ans = new ArrayList<>();
        dfsHelper(path,rt,visited,ans);
        System.out.println(ans);
        return ans;
    }

    public void dfsHelper(List<Unit> path, TrieNode rt, List<TrieNode> visited, List<List<Unit>> ans){
        if(rt == null){
            return;
        }
        if(visited.contains(rt)){
            return;
        }
        visited.add(rt);
        path.add(rt.value);
        if(rt.children.isEmpty()){
            List<Unit> pathCopy = new ArrayList<>(path);
            pathCopy.remove(0);
            Collections.reverse(pathCopy);
            ans.add(pathCopy);
        }
        for(TrieNode child : rt.children.values()){
            dfsHelper(path,child,visited,ans);
        }
        path.remove(path.size()-1);
        visited.remove(visited.size()-1);
    }

}
